package leetcode.D1000.T980;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-10 0:07:08 星期四
 */

class Solution {
    private int cnt=0, result=0, endx, endy, startx, starty, m, n;
    private int[] dx = new int[]{0, 0, -1, 1};
    private int[] dy = new int[]{-1, 1, 0, 0};
    public int uniquePathsIII(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if (grid[i][j] == 2) {
                    endx = i;
                    endy = j;
                } else if (grid[i][j] == 1) {
                    startx = i;
                    starty = j;
                } else if (grid[i][j] == 0) {
                    cnt++;
                }
            }
        }
        dfs(grid, 0, startx, starty);
        return result;
    }

    private void dfs(int[][] grid, int curCnt, int x, int y) {
        if (curCnt == cnt) {
            if (adj(x, y)) {
                result++;
            }
            return;
        }
        for(int i=0; i<4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (isValid(grid, nx, ny)) {
                grid[nx][ny] = -1;
                dfs(grid, curCnt+1, nx, ny);
                grid[nx][ny] = 0;
            }
        }
    }
    private boolean adj(int x, int y) {
        if (endx == x && Math.abs(y-endy)==1)
            return true;
        if (endy == y && Math.abs(x - endx)==1)
            return true;
        return false;
    }
    private boolean isValid(int[][] grid, int x, int y) {
        if (x<0||x>=m||y<=0||y>=n)
            return false;
        return grid[x][y] == 0;
    }
}